package com.wtgroup.demo.mianshi.算法.动态规划.暴力递归

import com.wtgroup.demo.common.judge.Judger
import com.wtgroup.demo.common.util.RandomUtil
import com.wtgroup.demo.common.util.Tools

/**
 * @author nisus
 * @version 0.1
 * @since 2023/5/11 10:07
 */
public class Q_最长公共字串 {

    static void main(String[] args) {
        test1()
    }

    private static void testTime() {
        String str1 = RandomUtil.randomNumbers(RandomUtil.randomInt(0, 20))
        String str2 = RandomUtil.randomNumbers(RandomUtil.randomInt(0, 20))
        D1 d1 = new D1()
        D1_DP ddp = new D1_DP()

        long cost1 = Tools.time("d1", 10, () -> {
            int res = d1.func(str1, str2)
        })
        long cost2 = Tools.time("d1_dp", 10, () -> {
            int res2 = ddp.func(str1, str2)
        })

        println "$cost1, $cost2, ${cost1 - cost2}"
    }

    private static test1() {
        Judger.of {
            // String str1 = "abc1z2b3"
            // String str2 = "ap123a"
            // String str1 = "20191120"
            // String str2 = "5802"
            String str1 = RandomUtil.randomNumbers(RandomUtil.randomInt(0, 10))
            String str2 = RandomUtil.randomNumbers(RandomUtil.randomInt(0, 10))
            int res = new D1().func(str1, str2)
            int res2 = new D1_DP().func(str1, str2)
            if (res != res2) {
                println str1
                println str2
                println "$res, $res2"
            }
            return res == res2;
        }.setIterCount(100).start().print()
    }


    static class D1 {

        int func(String str1, String str2) {
            if (str1 == null || str2 == null || str1.isEmpty() || str2.isEmpty()) {
                return null;
            }
            char[] char1 = str1.toCharArray()
            char[] char2 = str2.toCharArray()

            int ans = func0(char1, char2, 0, 0)

            return ans;
        }

        int func0(char[] char1, char[] char2, int start1, int start2) {
            int n1 = char1.length, n2 = char2.length
            if (start1 >= n1 || start2 >= n2) {
                return 0
            }

            int ans = 0;
            char[] anschar = null
            for (int i1 = start1; i1 < n1; i1++) {
                boolean isAlign = false
                int i2 = start2
                for (; i2 < n2; i2++) {
                    if (char1[i1] == char2[i2]) {
                        isAlign = true // 对齐上
                        break
                    }
                }
                if (!isAlign) {
                    continue
                }

                // i1 和 i2 对齐, 后面的递归
                // char[] subres = func0(char1, char2, i1 + 1, i2 + 1)
                // if (subres != null) {
                //     int ans1 = 1 + subres.length
                //     ans = Math.max(ans, ans1)
                // }
                int ans1 = 1 + func0(char1, char2, i1 + 1, i2 + 1)
                ans = Math.max(ans, ans1)
            }

            return ans;
        }

    }


    static class D1_DP {

        int func(String str1, String str2) {
            if (str1 == null || str2 == null || str1.isEmpty() || str2.isEmpty()) {
                return null;
            }
            // 假设只有 '0'~'9'
            char[] char1 = str1.toCharArray()
            char[] char2 = str2.toCharArray()
            int N1 = char1.length, N2 = char2.length

            int[][] dp = new int[N1+1][N2+1]
            for (i in 0..N1) {
                for (j in 0..N2) {
                    dp[i][j] = -1
                }
            }

            for (s1 in N1..0) {
                for (s2 in N2..0) {
                    int ans = func0(char1, char2, s1, s2, dp)
                }
            }

            return dp[0][0];
        }

        int func0(char[] char1, char[] char2, int start1, int start2, int[][] dp) {
            if (dp[start1][start2] > 0) {
                return dp[start1][start2]
            }
            int n1 = char1.length, n2 = char2.length
            if (start1 >= n1 || start2 >= n2) {
                return dp[start1][start2] = 0
            }

            int ans = 0;
            char[] anschar = null
            for (int i1 = start1; i1 < n1; i1++) {
                boolean isAlign = false
                int i2 = start2
                for (; i2 < n2; i2++) {
                    if (char1[i1] == char2[i2]) {
                        isAlign = true // 对齐上
                        break
                    }
                }
                if (!isAlign) {
                    continue
                }

                // i1 和 i2 对齐, 后面的递归
                // char[] subres = func0(char1, char2, i1 + 1, i2 + 1)
                // if (subres != null) {
                //     int ans1 = 1 + subres.length
                //     ans = Math.max(ans, ans1)
                // }
                // int ans1 = 1 + func0(char1, char2, i1 + 1, i2 + 1)
                int ans1 = 1 + dp[i1+1][i2+1]
                ans = Math.max(ans, ans1)
            }

            return dp[start1][start2] = ans;
        }

    }


}
